1. Field of the Invention
The present invention relates to an image processing apparatus, an image processing method, and an image forming apparatus including the image processing apparatus.
2. Description of the Related Art
Image forming apparatuses such as printers temporarily store image data in memories. When the image data is stored in the memories without any change, the memories are required to have high capacity, thereby increasing the price of the memories. In order to avoid such an increase in price, the image data is compressed and stored in the memories.
Such printers perform a printing process in the following manner, for example. The printer analyzes a page description language (PDL) that is produced by a computer, for example, and received through a network or the like and produces an intermediate language executable by a rendering unit. The rendering unit analyzes the intermediate language and draws an image after a gradation process to a band memory. The drawn image data is compression-coded by a compression coding algorithm for binary image and the produced encoded data is stored in a memory. In printing operation, the encoded data is read from the memory while being delayed for each of the color planes of cyan, magenta, yellow, and black (CMYK), and decoded, and the decoded data is transferred to printer engines, which process the data corresponding to the respective color planes of CMYK and print the image.
As a method of efficiently compressing data, a method of compressing data by universal coding has been put into practical use. The universal coding is a lossless data compression method and is applicable to various types of data (such as character codes and object codes) because statistical nature of information sources is not presupposed in data compression.
A typical universal coding is Ziv-Lempel coding. In the Ziv-Lempel coding, a universal type algorithm and an incremental parsing type algorithm have been proposed. A practical technique using the universal type algorithm is Lempel-Ziv-Storer-Syzmanaski (LZSS) coding.
In the coding algorithm of LZ77 coding, which is the base of the LZSS coding, target data for encoding is divided as a maximum length string of data matched with the data in past data string from an arbitrary position in the past data string and encoded as the duplicate of the past data string.
More specifically, a moving window that stores encoded input data and a lookahead buffer that stores data to be encoded are provided. The data string in the lookahead buffer are compared with all partial strings of the data string in the moving window, and a longest matching partial string in the moving window is obtained. In order to designate the longest matching partial string in the moving window, a set of “a start position of the longest matching partial string”, “a matching length”, and “a next symbol causing a mismatch” is encoded.
Then, the encoded data string in the lookahead buffer is shifted to the moving window and a new data string having the same data length as the encoded data string is input in the lookahead buffer. Thereafter, the same processing is repeated, so that data is decomposed into partial data strings and encoded.
In general, the LZSS coding needs to detect the longest matching with an input data string as many times as the number of moving windows storing the encoded input data. As a result, an amount of calculation is increased, but a high compression ratio can be obtained.
Another practical technique using the universal type algorithm in the Ziv-Lempel coding is Lempel, Ziv, Welch (LZW) coding. In the LZW coding, a rewritable dictionary is provided and input character strings are divided into different character strings. The character strings are designated with numbers in the order they appear and registered in the dictionary. In addition, a currently input character string is encoded by being represented only by a dictionary number of a longest matching character string registered in the dictionary. Compared with the LZSS coding, the LZW coding is lower in the compression ratio, but is simpler, easier in calculation, and can achieve higher speed processing. Thus, the LZW coding has been widely used for file compression in storage devices and data transfer, for example.
In the LZ77 technique, it takes long time in searching for the longest matching character string in coding. In order to speed up the LZ77 coding, it is effective to perform the search process with higher speed. A technique that performs run length coding on an index value coincident with a small dynamic dictionary by move to front (MTF) control of the dictionary is described in Japanese Patent No. 4,000,266.
The technique described in Japanese Patent No. 4000266, however, is inefficient when the length of a word to be registered in the dictionary is short. As a result, high speed processing is not expected. For example, when the length of the word registered in the dictionary is 1 byte and the depth of the dictionary is 64, the data length is only converted from 8 bits to 6 bits even when the index value is coincident with the dictionary. For a further increase in efficiency, the lengths of words in the dictionary need to be increased. The increase in length of words, however, causes the coincidence with the dictionary to be hardly achieved. To address such difficulties, the lengths of the words are obtained by period detection in Japanese Patent No. 4000266.
The encoding process using the period detection needs to use any of a two-path method or pipeline processing. In the two-path method, the encoding process is divided into two stages, which are a period detecting process and an encoding process. The data to be encoded is first passed to the stage of the period detecting process, in which the period of the data is obtained, and thereafter the data is passed to the stage of the encoding process, in which the encoding process is performed using the period obtained by the stage of the period detecting process. In this pipeline processing, the period detecting process and the encoding process are pipelined using working memories such as line memories.
The two-path method needs to take extra time because the coding is performed at the two stages. As a result, high speed processing is hardly achieved. In the pipeline processing, memories having a relatively large capacity need to be prepared as the working memories, resulting in an increase in costs. In this way, the related-art coding method using the LZ77 technique has a problem in that it is difficult to efficiently perform coding regardless of the data length for determining the coincidence with the data string.
Therefore, there is a need for an image processing apparatus enabling the compression coding of the image data to be more efficiently performed.